package com.c2b.algorithm.newcoder.heapStackQueue;

import java.util.Stack;

/**
 * <a href="https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj">有效括号序列</a>
 * <p>
 * 给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。<br>
 * 数据范围：字符串长度0≤n≤10000<br>
 * 要求：空间复杂度O(n)，时间复杂度O(n)<br>
 * </p>
 *
 * @author c2b
 * @since 2023/3/14 15:27
 */
public class BM0044IsValid_S {

    public boolean isValid(String s) {
        if (s.isEmpty()) {
            return true;
        }
        final char[] chars = s.toCharArray();
        final Stack<Character> stack = new Stack<>();
        for (char aChar : chars) {
            if (aChar == '(' || aChar == '[' || aChar == '{') {
                // 如果是'('、'['、'{'，直接入栈
                stack.push(aChar);
            } else {
                // 如果是')'、']'、'}'，需要栈非空并且栈顶元素与之匹配，否则返回false
                if (stack.empty()) {
                    return false;
                } else {
                    final Character character = stack.pop();
                    switch (aChar) {
                        case ')':
                            if (character != '(') {
                                return false;
                            }
                            break;
                        case ']':
                            if (character != '[') {
                                return false;
                            }
                            break;
                        case '}':
                            if (character != '{') {
                                return false;
                            }
                            break;
                    }
                }
            }
        }
        // 恰好栈中无元素，返回true。否则返回false
        return stack.empty();
    }
}
